package com.sjf.day02.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author <huangtang>
 * @since 2021/12/28 11:19
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        //int[] arr = new int[100000];
        //for (int i = 0; i < 100000; i++) {
        //    arr[i] = (int)(Math.random() * 1000000); //生产 0 - 100000的随机数
        //}
        //long t1 = System.currentTimeMillis();
        int[] temp = new int[arr.length]; //归并排序需要一个额外数组空间

        mergeSort(arr,0,arr.length-1,temp);

        System.out.println(Arrays.toString(arr));
        //System.out.println("归并排序用时："+(System.currentTimeMillis()-t1));  //14ms

    }

    /**
     * 分组加合并的方法
     * @param arr
     * @param left
     * @param right
     * @param temp
     */
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right)/2; //中间索引
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge2(arr,left,mid,right,temp);
        }

    }

    /**
     * 合并的方法
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left; //初始化i为左边索引
        int j = mid+1;//初始化j为右边有序数组初始索引
        int t = 0; //temp数组的当前索引

        //把左右两把数组填充到temp中去，直到有一边的数组处理完毕
        while(i <= mid && j <= right){ //i未达到中间索引，并且j未到达数组尾部
            if(arr[i]<=arr[j]){
                //如果左边有序序列的当前元素小于等于右边有序序列当前元素，就把左边的元素填充到temp中
                temp[t++] = arr[i++];
            }else{
                //否则把右边的元素填充到temp中
                temp[t++] = arr[j++];
            }
        }
        //把有剩余数据的数组直接填充到temp数组的后面部分
        while(i <= mid){
            //说明左边有序序列还有剩余，则直接填充到temp中
            temp[t++] = arr[i++];
        }
        while(j <= right){
            //说明右边还有剩余
            temp[t++] = arr[j++];
        }
        //将temp数组重新拷贝到arr
        //并不是每次都拷贝到temp数组
        t = 0;
        int tempLeft = left;
        while(tempLeft<=right){
            arr[tempLeft++] = temp[t++];
        }
    }

    public static void merge2(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid+1;
        int t = 0;//遍历插入temp数组的指针索引
        //把左右两把数组填充到temp中去，直到有一边的数组处理完毕
        while(i <= mid && j <= right){
            if(arr[i]<arr[j]){
                temp[t++] = arr[i++];//如果左边的数小于中轴数，则将左边的数填充到temp中
            }else{
                temp[t++] = arr[j++];//反之亦然
            }
        }
        //把有剩余数据的数组直接填充到temp数组的后面部分
        while(i <= mid){
            temp[t++] = arr[i++];
        }
        while(j <= right){
            temp[t++] = arr[j++];
        }
        //将temp数组重新拷贝到arr
        //并不是每次都拷贝到temp数组
        t = 0;
        int tempLeft = left;
        while(tempLeft<=right){
            arr[tempLeft++] = temp[t++];
        }
    }


}
